package com.shm.leetcode;
/**
 * @author: shm
 * @dateTime: 2020/11/3 9:52
 * @description: 941. 有效的山脉数组
 * 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
 *
 * 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
 *
 * A.length >= 3
 * 在 0 < i < A.length - 1 条件下，存在 i 使得：
 * A[0] < A[1] < ... A[i-1] < A[i]
 * A[i] > A[i+1] > ... > A[A.length - 1]
 *
 *
 * 示例 1：
 *
 * 输入：[2,1]
 * 输出：false
 * 示例 2：
 *
 * 输入：[3,5,5]
 * 输出：false
 * 示例 3：
 *
 * 输入：[0,3,2,1]
 * 输出：true
 *
 * 提示：
 *
 * 0 <= A.length <= 10000
 * 0 <= A[i] <= 10000 
 */
public class ValidMountainArray {
    public boolean validMountainArray(int[] A) {
        int n = A.length;
        if(n<3){
            return false;
        }
        for(int i=1;i<n-1;i++){
            int k = 0;
            for(int j=0;j<n;j++){
                if(j>0&&j<=i&&A[j]<=A[j-1]){
                    break;
                }
                if(j>i&&A[j]>=A[j-1]){
                    break;
                }
                k=j;
            }
            if(k==n-1){
                return true;
            }
        }
        return false;
    }

    /**
     * @author: shm
     * @dateTime: 2020/11/3 9:52
     * @description: 方法一：线性扫描
     * 按题意模拟即可。我们从数组的最左侧开始向右扫描，直到找到第一个不满足 A[i] < A[i + 1]A[i]<A[i+1] 的下标 ii，那么 ii 就是这个数组的最高点的下标。
     * 如果 i = 0i=0 或者不存在这样的 ii（即整个数组都是单调递增的），那么就返回 \text{false}false。
     * 否则从 ii 开始继续向右扫描，判断接下来的的下标 jj 是否都满足 A[j] > A[j + 1]A[j]>A[j+1]，若都满足就返回 \text{true}true，否则返回 \text{false}false。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 是数组 AA 的长度。
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/valid-mountain-array/solution/you-xiao-de-shan-mai-shu-zu-by-leetcode-solution/
     */
    public boolean validMountainArray_2(int[] A) {
        int n = A.length;
        if(n<3){
            return false;
        }
        int i = 0;
        // 递增扫描
        while (i+1<n&&A[i]<A[i+1]){
            i++;
        }
        // 最高点不能是数组的第一个位置或最后一个位置
        if (i==0||i==n-1){
            return false;
        }
        // 递减扫描
        while (i+1<n&&A[i]>A[i+1]){
            i++;
        }
        return i==n-1;
    }

    public boolean validMountainArray_3(int[] A) {
        int n = A.length;
        int left = 0;
        int right = n-1;
        //从左边往右边找，一直找到山峰为止
        while (left+1<n&&A[left]<A[left+1]){
            left++;
        }
        //从右边往左边找，一直找到山峰为止
        while (right>0&&A[right]<A[right-1]){
            right--;
        }
        //判断从左边和从右边找的山峰是不是同一个
        return left>0&&right<n-1&&left==right;
    }
}
